COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00018 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a58.tex[154,phy] \today\hfill}

\newbox\bgcrc \setbox\bgcrc=\hbox{$\bigcirc$}
\def\orightarrow{\mathop{\hbox to 0pt{\kern-.5pt\raise1pt\hbox to 1\wd\bgcrc{\hfil
	$\scriptstyle\rightarrow$\hfil}\hss}\bigcirc}}

\parskip 5pt
\bigskip
\line{\bf Kleene's Theorem and Digraphs\hfill}

A {\sl digraph\/} $G$ is a set $V$ of {\sl vertices\/} (singular: {\sl vertex\/})
and a set $A\subseteq V\times V$ of {\sl arcs\/}. A~{\sl path\/} in~$G$
is a sequence $\langle v↓1,v↓2,\ldots,v↓n\rangle$ of vertices, $n≥1$,
where each $\langle v↓i,v↓{i+1}\rangle$ is an arc. 
We say the path is from~$v↓1$, and to~$v↓n$; we also say
$v↓1$ is the {\sl source\/}, and $v↓2$ the {\sl sink\/},
of the path. In particular, each arc is a path, and for each vertex~$v$
there is a null path ${\rm null}↓v=\langle v\rangle$.


The operation
$\vec{\otimes}$ of {\sl catenation\/} combines two paths:
$\langle v↓1,v↓2,\ldots,v↓m\rangle \vec{\otimes}
\langle v↓m,v↓{m+1},\ldots,v↓n\rangle
=\langle v↓1,v↓2,\ldots,v↓n\rangle$. Catenation is a partial function,
defined only when the sink of the first path is the source of the
second. Catenation is associative:
$(p↓1\vec{\otimes} p↓2)\vec{\otimes} p↓3
=p↓1\vec{\otimes} (p↓2\vec{\otimes} p↓3)$.

By the usual set extension, catenation is extended to sets of paths:
$X↓1\vec{\otimes} X↓2=\{\,p↓1\vec{\otimes} p↓2\mid p↓i\in X↓i\,\}$.
Any pairs where the sink of~$p↓i$ is not the source of~$p↓2$ are
naturally excluded. We define $X↑i$ by $X↑0=\Lambda =\{\,\langle v\rangle
\mid v\in V\,\}$, the set of all null paths, $X↑{i+1}=X↑i\vec{\otimes} X$.
In consequence, $X↑1=X$. We define the {\sl iteration\/} of~$X$ by
$X\!\!\uparrow\, =\bigcup↓{i≥0}X↑i$. The major mathematical properties of
sets of paths are these:

\medskip
\halign{\qquad\qquad #\hfil\cr
$\displaystyle{\left.\eqalign{%
&\!(X↓1\,\vec{\otimes}\, X↓2)\,\vec{\otimes}\, X↓3
=X↓1\,\vec{\otimes}\,(X↓2→X↓3)\cr
&\!(X↓1\cup X↓2)\cup X↓3=X↓1\cup(X↓2\cup X↓3)\cr}
\right\}}$\quad associativity\cr
\noalign{\smallskip}
$X↓1\cup X↓2=X↓2\cup X↓1$\quad commutativity\cr
\noalign{\smallskip}
$\displaystyle{\left.\eqalign{%
&\!\Lambda\,\vec{\otimes}\, X=X\,\vec{\otimes}\,\Lambda\cr
&\!\emptyset\cup X=X=X\cup\emptyset\cr}
\right\}}$\quad identity\cr
\noalign{\smallskip}
$\displaystyle{\left.\eqalign{%
&\!(X↓1\cup X↓2)\,\vec{\otimes}\, Y=
(X↓1\,\vec{\otimes}\, Y)\cup(X↓2\,\vec{\otimes}\, Y)\cr
&\!X\,\vec{\otimes}\, (Y↓1\cup Y↓2)=(X\,\vec{\otimes}\, Y↓1)\cup 
(X\,\vec{\otimes}\,Y↓2)\cr}
\right\}}$\quad distributivity\cr
\noalign{\smallskip}
$X↑0=\Lambda$\cr
\noalign{\smallskip}
$X↑{i+1}=X↑i\,\vec{\otimes}\, X$\cr
\noalign{\smallskip}
$X↑{i+j}=X↑i\,\vec{\otimes}\, X↑j$\cr
\noalign{\smallskip}
$X\!\!\uparrow\, =\Lambda\cup X\!\!\uparrow\, \vec{\otimes}\, X$\cr
\noalign{\smallskip}
$X\!\!\uparrow\uparrow\, =X\!\!\uparrow$\cr
\noalign{\smallskip}
$X\!\!\uparrow\,\vec{\otimes}\,X\!\!\uparrow\;=X\!\!\uparrow$\cr}

\smallskip
Some path sets can be built up from single paths by union, catenation,
and iteration. These are called {\sl regular\/} path sets. Axiomatically:

\smallskip
\disleft 20pt:(1):
If $p$ is a path, $\{p\}$ is regular; $\{p\}$ is abbreviated to~$p$
where no ambiguity arises.

\smallskip
\disleft 20pt:(2):
The empty set $\emptyset$ is regular.

\smallskip
\disleft 20pt:(3):
(Closure) If $X$ and $Y$ are regular path sets, so are 
$(X\vec{\otimes} Y)$, $(X\cup Y)$, and $(X\!\!\uparrow)$. Parentheses are
omitted where no ambiguity arises.

\smallskip
\disleft 20pt:(4):
(Induction) The above are the only regular path sets. Therefore, to prove
that all regular path sets have a property~$Q$, it suffices to prove
$Q(\emptyset)$, $Q(\{p\})$, $Q(X)∧Q(Y)⊃Q(X\vec{\otimes} Y)∧Q(X\cup Y)$,
and $Q(X)⊃Q(X\!\!\uparrow)$.

\vfill\eject

An alternate to the first axiom is

\smallskip
\disleft 20pt:(1$'$):
If $p$ is an arc or a null path, $\{p\}$ is regular.

The {\sl regular path expressions\/} are those consisting of individual
path names and the symbols $\emptyset$, $\vec{\otimes}$, $\cup$, and~$\uparrow$,
with parentheses as needed. An example of the use of the induction axiom
is that the regular path sets are exactly those named by regular path
expressions.

We say a path is {\sl via\/} $S\subseteq V$ if all vertices, with the possible
exception of the first and last, belong to~$S$. Let $P↓{i,S,k}$ be the
set of paths from~$i$ via~$S$ to~$k$. Let $P↓{V↓-,S,V↓+}$ be the set of
paths from $i\in V↓-\subseteq V$ via~$S$ to $k\in V↓+\subseteq V$. Let
$P↓{i,k}=P↓{i,V,k}$, $P↓{V↓-,V↓+}=P↓{V↓-,V,V↓+}$. By induction on the
cardinality of~$S$ we prove:

\proclaim Kleene's Theorem. In a finite digraph, the set of paths from
$V↓-$ to~$V↓+$ is regular.

\noindent
{\bf Proof.} $P↓{i,\emptyset,k}$ consists of any arcs and null paths 
from~$i$ to~$k$, and is clearly regular. If $S'=S\& j$ (the disjoint union
of~$S$ and~$\{j\}$), $P↓{i,S',k}$ may be partitioned into paths that do
not or do contain~$j$, giving
$P↓{i,S',k}=P↓{i,S,k}\cup P↓{i,S,j}(P↓{j,S,j}\!\!\uparrow)P↓{j,S,k}$.
By evaluating $P↓{i,S,k}$ for all~$i$ and~$k$, for an expanding sequence
of sets~$S$, we end with a regular path expression for each $P↓{ik}$; this
algorithm has other uses, mentioned later. The algorithm does one step
for each choice of $i,j,k\in V$, so it performs about $|V|↑3$ steps.
Finally, $P↓{V↓-,V↓+}$ is a finite union of $P↓{ik}$ for
$i\in V↓-$, $k\in V↓+$, and is therefore regular.\quad\blackslug

Let $h$ be a {\sl labelling\/} of digraph $G$: a function from arcs of~$G$
to a monoid~$M$. Then $h$ may be extended as a homomorphism from all
paths of~$G$; let $h(\langle v\rangle)$ be the identity of~$M$, and
$h(p↓1\vec{\otimes} p↓2)=h(p↓1)\vec{\otimes} h(p↓2)$.
We may further extend~$h$ as a homomorphism from sets of paths in~$G$
to the monoid [semiring?] of subsets of~$M$, by 
$h(X)=\{\,h(p)\mid p\in X\,\}$.

If $X$ is a regular path set, there is a regular monoid expression 
for $h(X)$. By the induction axiom, it suffices to show:

\smallskip
\halign{\qquad\qquad #\hfil\cr
$h(\emptyset)=\emptyset$\cr
$h(\langle v\rangle)=\epsilon↓M$\cr
$h(\langle v↓1,v↓2\rangle)=\hbox{the appropriate element of $M$}$\cr
$h(X\cup Y)=h(X)\cup h(Y)$\cr
$h(X\vec{\otimes} Y)=h(X)\vec{\otimes} h(Y)$\cr
$h(X\!\!\uparrow)\,=h(X)↑{\ast}$\cr}

Let the monoid be the monoid of regular languages over~$\Sigma$. Then 
$h$~labels every
regular path set in~$G$ with a regular language over~$\Sigma$.
Specifically, the strings accepted by a finite machine, being the labels
on the regular set of paths from~$V↓-$ to~$V↓+$, are a regular language.
In fact, after constructing the regular path expression for the finite
machine, it is sufficient just to replace null paths by~$\epsilon$,
arcs by their labels, $\vec{\otimes}$ by~$\vec{\otimes}$, and $\uparrow$ by~$\ast$,
to get the regular language expressions for the language the machine accepts.

Let every arc in $G$ be labelled with a length, a number $≥0$. This can be
extended homomorphically as a labelling of paths by
$h(\langle v\rangle)=0$, $h(p↓1\vec{\otimes} p↓2)=h(p↓1)+h(p↓2)$.
It can be further extended from sets of paths to their least lengths,
$h(X)=\min\{\,h(p)\mid p\in X\,\}$, with the properties:

\smallskip
\halign{\qquad\qquad #\hfil\quad&#\hfil\cr
$h(\emptyset)=∞$\cr
$h(\langle v\rangle)=0$\cr
$h(X\cup Y)=\min\bigl(h(X),h(Y)\bigr)$\cr
$h(X\vec{\otimes} Y)=h(X)+h(Y)$&provided that a single vertex is the\cr
&only sink in $X$ and the only source in $Y$\cr
$h(X\!\!\uparrow)=0$\cr}

\noindent
The algorithm used in Kleene's theorem can be adapted (Floyd's algorithm)
to give directly the length of the shortest paths, and, if desired, the
first arc of the shortest path. The analogous (Warshall's) algorithm
determines the existence of a path for each source and sink.

\vfill\eject

\centerline{[RWF: rough draft]}

\bigskip
\line{\bf Shortest-path algorithm as an application of Kleene's Theorem.\hfil}

\medskip
Define a semiring with elements $\{\,\langle x,y\rangle\mid x\in {\bf R}\,\&\,∞,
x≥0\,,\,y\in V↑{\ast},\,|y|≤k\,\}$
(order them lexicographically); a~set of paths that maps into
$\langle x,y\rangle$ will have shortest path length~$x$, and that shortest
path will have~$y$ as its first $k$~vertices. The operations of the semiring are
$$\eqalign{\langle l↓1,s↓1\rangle\otimes\langle l↓2,s↓2\rangle
&=\langle l↓1+l↓2,\,{\rm first}\;k(s↓1\otimes s↓2)\rangle\cr
\langle l↓1,s↓1\rangle\oplus\langle l↓2,s↓2\rangle
&=\min(\langle l↓1,s↓1\rangle\,,\,\langle l↓2,s↓2\rangle)\cr
\langle l↓1,s↓1\rangle\!\!\uparrow&=\langle 0,\epsilon\rangle\cr}$$

\bigskip
The Kleene algorithm is

\smallskip
\halign{\qquad\qquad#\hfil\cr
$S←\emptyset$;\cr
{\bf for} $i$, $k$ {\bf do}\cr 
{\bf if} $i=k$ {\bf then} $HP[i,s,k]←\langle 0,i\rangle$\cr
{\bf else if} {\sl arc\/}$(i,k)$ {\bf then} $HP[i,s,k]←\langle l,i-k\rangle$\cr
{\bf else} $HP[i,s,k]←\langle ∞,{\rm anything}\rangle$;\cr
{\bf for} $j\in V$ {\bf do}\cr
\qquad $T←S\,\&\,j$;\cr
\qquad {\bf for} $i,k\in V$ {\bf do}\cr
\qquad $HP[i,T,k]←HP[i,s,k]\oplus HP[i,s,j]\otimes HP[j,s,j]\!\!\uparrow\otimes 
HP[j,s,k]$;\cr
\qquad $S←T$\cr}

\smallskip\noindent
Invariant: $HP[i,s,k]=H(P↓{i,s,k})$. Represent $s$ by largest element~$j$.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
September 22, 1986.
%revised date;
%subsequently revised.

\bye